package q556_nextGreaterElement;

public class Solution_1 {
    /*
    这种做法完全参照q31
    即下一个排列的题解 通过使用双指针来找出下一个排列
    然后转换回数字即可
     */
    public int nextGreaterElement(int n) {
        int m = n, count = 0;
        while (m > 0) {
            m /= 10;
            ++count;
        }
        if (count == 1) return -1;
        int[] nums = new int[count];
        for (int i = nums.length - 1; i >= 0; i--) {
            nums[i] = n % 10;
            n /= 10;
        }

        int left = nums.length - 2;
        int right = nums.length - 1;

        while (left >= 0) {
            if(nums[left] >= nums[left + 1]){
                left--;
            }else {
                while(right > left){
                    if (nums[left] >= nums[right]) {
                        right--;
                    }else {
                        break;
                    }
                }
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                BubbleSort(nums,left + 1);
                break;
            }


        }

        if(left == -1) return -1;
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (ans > Integer.MAX_VALUE / 10 && i < nums.length - 1) return -1;
            ans = ans * 10 + nums[i];
        }

        return ans;
    }

    public static void BubbleSort(int[] arr,int start) {
        for (int x = start; x < arr.length - 1; x++) {
            for (int y = start; y < arr.length - 1 - x + start; y++) {
                if (arr[y] > arr[y + 1]) {
                    int temp = arr[y];
                    arr[y] = arr[y + 1];
                    arr[y + 1] = temp;
                }
            }
        }
    }
}
